1. Field of the Invention
The present invention relates to a collision detection method for objects in a scene and, more particularly, to a collision detection method for polygonal deformable objects using OpenGL.
2. Discussion of Related Art
Under many interactive virtual environments, such as surgery simulations, there is a need to determine if two or more objects in a scene are colliding with each other. In general, collision between objects may be detected if there are surfaces of the objects that are touching and/or intersecting with each other. For realistic interactions or simulations in virtual environments, collision detection and calculations require good timing performance and accuracy.
The most general and versatile methods to detect collisions between polygonal models are based on bounding volume hierarchies. Hierarchies of bounding volumes provide a fast way to perform collision detection between complex models. These methods are primarily categorized by the type of bounding volume that is used at each node of a hierarchy tree. These methods include Object Oriented Bounding Boxes (OOBB), axis aligned bounding boxes (AABB), or bounding spheres. The OOBB method, used by a Robust and Accurate Polygon Interference Detection (RAPID) system, is very efficient in the collision query.
In the OOBB method, the collision detection is performed by testing if bounding boxes from different objects overlap. However, it is necessary to rebuild the hierarchy tree or refit it at every step when deformable objects are concerned. This is a time consuming task that makes this method not suitable for use with deformable objects.
The AABB method is also a fast method for collision query, which can be updated for object's deformation. In AABB trees, the boxes are aligned to the axes of the model's local coordinate system and, thus, all the boxes in a tree have the same orientation. An AABB tree is constructed top-down, by recursive subdivision. At each recursion step, the smallest AABB of the set of primitives is computed, and the set is split by ordering the primitives with respect to a well-chosen partitioning plane. This process continues until each subset contains one element (i.e. primitive). Thus, an AABB tree is made with a set of n leaves and n−1 internal nodes. However, updating its tree structure is still the bottleneck for this method. The cost of the tree update increases significantly with the number of polygons using the conventional AABB method.
The main limitation of the above methods is that in the case of deformable objects the hierarchy trees have to be updated (or re-built) at every step of the simulation. This is a time-consuming step that significantly reduces the efficiency of these methods.
One approach to reduce the time consuming step is to use graphics hardware acceleration for collision detection. However, this approach is limited to collisions between two-dimensional objects, or to some specialized three-dimensional scenes, such as those whose objects collide only in a two-dimensional plane.
Another well-known approach is to use the selection mode of the OpenGL system to identify collisions between polygonal surfaces. However, it is also limited to collisions between a deformable polygonal surface and an object with a very simple shape, such as a cylinder or a box. Furthermore, efficiency of the performance according to this method significantly decreases with the increase of the object's number of polygons. Therefore, it is limited to objects with relatively small number of polygons.
A need, therefore, exists for a collision detection method using the OpenGL system which allows a fast and accurate way to detect the collisions between the individual polygons of deformable objects.